<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>背包问题</title>
  </head>
  <body>
    <script>
      function sortMax(widget, money, all) {
        let len = widget.length;
        let fullBack = [[]];
        fullBack[-1] = new Array(all + 1).fill(0);
        for (let i = 0; i < all; i++) {
          if (widget[0] < i) {
            fullBack[0][i] = money[0];
          } else {
            fullBack[0][i] = 0;
          }
        }
        for (let i = 1; i < len; i++) {
          fullBack[i]= new Array(all).fill(0)
          for (let j = 0; j < all; j++) {
            if (widget[i] > j) {
              fullBack[i][j] = fullBack[i - 1][j];
            } else {
              fullBack[i][j] = Math.max(
                fullBack[i - 1][j],
                fullBack[i - 1][j - widget[i]] + money[i]
              );
            }
            console.log(fullBack)
          }
        }
        return fullBack[len-1][all-1];
        // console.log(fullBack);
      }

      // sortMax([2, 2, 6, 5, 4], [6, 3, 5, 4, 6], 10);
      console.log(sortMax([2, 2, 6, 5, 4], [6, 3, 5, 4, 6], 10));
    </script>
  </body>
</html>
